﻿#define _CRT_SECURE_NO_WARNINGS

#include "LT.h"


LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->prev = node->next = node;//一个闭环的链
}
//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}
//初始化
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);//创建一个哨兵位
	return phead;
}


//销毁
void LTDestroy(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* ptail = pcur;
		pcur = pcur->next;
		free(ptail);
		ptail = NULL;
	}

	free(phead);
	phead = NULL;
}


//展示
void LTPrint(LTNode* phead)//最开始的phead是哨兵位，不用打印
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)//到哨兵位前终止打印
	{
		printf("%d ", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}


bool LTEmpty(LTNode* phead);


void LTPushBack(LTNode* phead, LTDataType x)
{//尾插，就相当于在哨兵位前插入
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	
	//对应一下
	//phead->prev				phead	1
	//phead->prev	newnode		phead	2
	//那么就有
	//原来的phead->prev = newnode->prev(看第2行)
	//原来的phead->prev->next = newnode(看第2行)
	//现在的newnode->next = phead(看第2行)
	//现在的phead->prev = newnode(看第2行)

	newnode->prev = phead->prev;
	phead->prev->next = newnode;

	newnode->next = phead;
	phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{//尾删，相当于把哨兵位前一个节点删除
	assert(phead);
	
	//对应一下
	//phead->prev->prev		phead->prev		phead
	//phead->prev->prev						phead

	LTNode* ptail = phead->prev;

	ptail->prev->next = phead;
	phead->prev = ptail->prev;

	free(ptail);
	ptail = NULL;
}
void LTPushFront(LTNode* phead, LTDataType x)
{//头插，就相当于在哨兵位后插入
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	//对应一下
	//phead					phead->next
	//phead		newnode		phead->next

	newnode->next = phead->next;
	phead->next->prev = newnode;
	
	newnode->prev = phead;
	phead->next = newnode;
}
void LTPopFront(LTNode* phead)
{//头删，就相当于把哨兵位后一个节点删除
	assert(phead);

	//对应一下
	//phead		phead->next		phead->next->next
	//phead						phead->next->next

	LTNode* ptail = phead->next;

	ptail->next->prev = phead;
	phead->next = ptail->next;

	free(ptail);
	ptail = NULL;
}


//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);

	//对应一下
	//pos					pos->next
	//pos		newnode		pos->next
	newnode->next = pos->next;
	pos->next->prev = newnode;

	newnode->prev = pos;
	pos->next = newnode;
}
//删除pos位置后的节点
void LTErase(LTNode* pos)
{
	assert(pos);

	//对应一下
	//pos	pos->next	pos->next->nxet
	//pos				pos->next->next

	LTNode* ptail = pos->next;

	pos->next = ptail->next;
	ptail->next->prev = pos;

	free(ptail);
	ptail = NULL;
}


//找到某数值，并返回节点指针
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}

	return NULL;
	printf("未找到\n");
}